home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / Other Langs / mpw yacc ƒ src / conflicts.c < prev    next >
C/C++ Source or Header  |  1989-11-19  |  5KB  |  282 lines
  1. #include <stdio.h>
  2. #include "defs.h"
  3. #include "dep.h"
  4. #include "new.h"
  5. #include "files.h"
  6. #include "gram.h"
  7. #include "state.h"
  8.  
  9. extern int tokensetsize;
  10. extern short *accessing_symbol;
  11. extern shifts **shift_table;
  12. extern unsigned *LA;
  13. extern short *LAruleno;
  14. extern short *lookaheads;
  15. extern char **symbol_name;
  16.  
  17. char any_conflicts;
  18. char *conflicts;
  19.  
  20. static unsigned *shiftset;
  21. static unsigned *lookaheadset;
  22. static int src_total;
  23. static int rrc_total;
  24. static int src_count;
  25. static int rrc_count;
  26.  
  27.  
  28.  
  29. initialize_conflicts()
  30. {
  31.   register int i;
  32.  
  33.   conflicts = NEW2(nstates, char);
  34.   shiftset = NEW2(tokensetsize, unsigned);
  35.   lookaheadset = NEW2(tokensetsize, unsigned);
  36.  
  37.   any_conflicts = 0;
  38.  
  39.   for (i = 0; i < nstates; i++)
  40.     set_conflicts(i);
  41. }
  42.  
  43.  
  44.  
  45. set_conflicts(state)
  46. int state;
  47. {
  48.   register int i;
  49.   register int k;
  50.   register shifts *shiftp;
  51.   register unsigned *fp2;
  52.   register unsigned *fp3;
  53.   register unsigned *fp4;
  54.   register unsigned *fp1;
  55.   register int symbol;
  56.  
  57.   for (i = 0; i < tokensetsize; i++)
  58.     lookaheadset[i] = 0;
  59.  
  60.   shiftp = shift_table[state];
  61.   if (shiftp)
  62.     {
  63.       k = shiftp->nshifts;
  64.       for (i = 0; i < k; i++)
  65.     {
  66.       symbol = accessing_symbol[shiftp->shifts[i]];
  67.       if (ISVAR(symbol)) break;
  68.       SETBIT(lookaheadset, symbol);
  69.     }
  70.     }
  71.  
  72.   k = lookaheads[state + 1];
  73.   fp4 = lookaheadset + tokensetsize;
  74.  
  75.   for (i = lookaheads[state]; i < k; i++)
  76.     {
  77.       fp1 = LA + i * tokensetsize;
  78.       fp2 = fp1;
  79.       fp3 = lookaheadset;
  80.  
  81.       while (fp3 < fp4)
  82.     {
  83.       if (*fp2++ & *fp3++)
  84.         {
  85.           conflicts[state] = 1;
  86.           any_conflicts = 1;
  87.           return;
  88.         }
  89.     }
  90.  
  91.       fp2 = fp1;
  92.       fp3 = lookaheadset;
  93.  
  94.       while (fp3 < fp4)
  95.     *fp3++ |= *fp2++;
  96.     }
  97. }
  98.  
  99.  
  100.  
  101. conflict_log()
  102. {
  103.   register int i;
  104.  
  105.   src_total = 0;
  106.   rrc_total = 0;
  107.  
  108.   for (i = 0; i < nstates; i++)
  109.     {
  110.       if (conflicts[i])
  111.     {
  112.       count_sr_conflicts(i);
  113.       count_rr_conflicts(i);
  114.       src_total += src_count;
  115.       rrc_total += rrc_count;
  116.     }
  117.     }
  118. }
  119.   
  120.  
  121.  
  122. verbose_conflict_log()
  123. {
  124.   register int i;
  125.  
  126.   src_total = 0;
  127.   rrc_total = 0;
  128.  
  129.   for (i = 0; i < nstates; i++)
  130.     {
  131.       if (conflicts[i])
  132.     {
  133.       count_sr_conflicts(i);
  134.       count_rr_conflicts(i);
  135.       src_total += src_count;
  136.       rrc_total += rrc_count;
  137.  
  138.       fprintf(verbose_file, "State %d contains", i);
  139.  
  140.       if (src_count == 1)
  141.         fprintf(verbose_file, " 1 shift/reduce conflict");
  142.       else if (src_count > 1)
  143.         fprintf(verbose_file, " %d shift/reduce conflicts", src_count);
  144.  
  145.       if (src_count > 0 && rrc_count > 0)
  146.         fprintf(verbose_file, " and");
  147.  
  148.       if (rrc_count == 1)
  149.         fprintf(verbose_file, " 1 reduce/reduce conflict");
  150.       else if (rrc_count > 1)
  151.         fprintf(verbose_file, " %d reduce/reduce conflicts", rrc_count);
  152.  
  153.       putc('.', verbose_file);
  154.       putc('\n', verbose_file);
  155.     }
  156.     }
  157.  
  158.   total_conflicts();
  159. }
  160.  
  161.  
  162.  
  163. count_sr_conflicts(state)
  164. int state;
  165. {
  166.   register int i;
  167.   register int k;
  168.   register int mask;
  169.   register shifts *shiftp;
  170.   register unsigned *fp1;
  171.   register unsigned *fp2;
  172.   register unsigned *fp3;
  173.   register int symbol;
  174.  
  175.   src_count = 0;
  176.  
  177.   shiftp = shift_table[state];
  178.   if (!shiftp) return;
  179.  
  180.   for (i = 0; i < tokensetsize; i++)
  181.     {
  182.       shiftset[i] = 0;
  183.       lookaheadset[i] = 0;
  184.     }
  185.  
  186.   k = shiftp->nshifts;
  187.   for (i = 0; i < k; i++)
  188.     {
  189.       symbol = accessing_symbol[shiftp->shifts[i]];
  190.       if (ISVAR(symbol)) break;
  191.       SETBIT(shiftset, symbol);
  192.     }
  193.  
  194.   k = lookaheads[state + 1];
  195.   fp3 = lookaheadset + tokensetsize;
  196.  
  197.   for (i = lookaheads[state]; i < k; i++)
  198.     {
  199.       fp1 = LA + i * tokensetsize;
  200.       fp2 = lookaheadset;
  201.  
  202.       while (fp2 < fp3)
  203.     *fp2++ |= *fp1++;
  204.     }
  205.  
  206.   fp1 = shiftset;
  207.   fp2 = lookaheadset;
  208.  
  209.   while (fp2 < fp3)
  210.     *fp2++ &= *fp1++;
  211.  
  212.   mask = 1;
  213.   fp2 = lookaheadset;
  214.   for (i = 0; i < ntokens; i++)
  215.     {
  216.       if (mask & *fp2)
  217.     src_count++;
  218.  
  219.       mask <<= 1;
  220.       if (mask == 0)
  221.     {
  222.       mask = 1;
  223.       fp2++;
  224.     }
  225.     }
  226. }
  227.  
  228.  
  229.  
  230. count_rr_conflicts(state)
  231. int state;
  232. {
  233.   register int i;
  234.   register int j;
  235.   register int count;
  236.   register unsigned mask;
  237.   register unsigned *baseword;
  238.   register unsigned *wordp;
  239.   register int m;
  240.   register int n;
  241.  
  242.   rrc_count = 0;
  243.  
  244.   m = lookaheads[state];
  245.   n = lookaheads[state + 1];
  246.  
  247.   if (n - m < 2) return;
  248.  
  249.   mask = 1;
  250.   baseword = LA + m * tokensetsize;
  251.   for (i = 0; i < ntokens; i++)
  252.     {
  253.       wordp = baseword;
  254.  
  255.       count = 0;
  256.       for (j = m; j < n; j++)
  257.     {
  258.       if (mask & *wordp)
  259.         count++;
  260.  
  261.       wordp += tokensetsize;
  262.     }
  263.  
  264.       if (count >= 2) rrc_count++;
  265.  
  266.       mask <<= 1;
  267.       if (mask == 0)
  268.     {
  269.       mask = 1;
  270.       baseword++;
  271.     }
  272.     }
  273. }
  274.  
  275.  
  276. finalize_conflicts()
  277. {
  278.   FREE(conflicts);
  279.   FREE(shiftset);
  280.   FREE(lookaheadset);
  281. }
  282.